package com.zjsru.oneDay202209;

import java.util.Arrays;

/**
 * @Author: likew
 * @Date: 2022/9/20
 *  划分为k个相等的子集
 *  给定一个整数数组  nums 和一个正整数 k，找出是否有可能把这个数组分成 k 个非空子集，其总和都相等。
 *
 *  输入： nums = [4, 3, 2, 3, 5, 2, 1], k = 4
 * 输出： True
 * 说明： 有可能将其分成 4 个子集（5），（1,4），（2,3），（2,3）等于总和。
 *
 * 输入: nums = [1,2,3,4], k = 3
 * 输出: false
 */
public class CanPartitionKSubsets {
    
    /**
     * cur 为当前集合的元素和（初始值为 00）；
     * cnt 是已凑成多少个总和为 tt 的集合（初始值为 00，当 cnt = k 时，我们搜索到了合法方案，返回 true，否则对 cnt 进行加一操作，并将 cur 置零，搜索下个集合）；
     * booleans 用于记录哪些 nums[i]已被使用；
     * idx 是搜索关键，其含义为搜索空间的分割点。即对于当前正在搜索的集合，我们不会每次都扫描整个 nums 来找添加到该集合的下一个元素，而是能够明确下一个元素必然在 idx的左边或右边。
     * */
    int[] nums;
    
    int n, t, k;
    
    public boolean canPartitionKSubsets(int[] _nums, int _k) {
        nums = _nums;
        k = _k;
        int tot = 0;
        for (int x : nums) {
            tot += x;
        }
        // 可行性剪枝
        if (tot % k != 0) {
            return false;
        }
        Arrays.sort(nums);
        n = nums.length;
        t = tot / k;
        return dfs(n - 1, 0, 0, new boolean[n]);
    }
    
    private boolean dfs(int idx, int cur, int cnt, boolean[] booleans) {
        if (cnt == k) {
            return true;
        }
        if (cur == t) {
            return dfs(n - 1, 0, cnt + 1, booleans);
        }
        // 顺序性剪枝
        for (int i = idx; i >= 0; i--) {
            // 可行性剪枝
            if (booleans[i] || cur + nums[i] > t) {
                continue;
            }
            booleans[i] = true;
            if (dfs(i - 1, cur + nums[i], cnt, booleans)) {
                return true;
            }
            booleans[i] = false;
            // 可行性剪枝
            if (cur == 0) {
                return false;
            }
        }
        return false;
    }
    
    public static void main(String[] args) {
        CanPartitionKSubsets canPartitionKSubsets = new CanPartitionKSubsets();
        int[] nums = new int[]{4, 3, 2, 3, 5, 2, 1};
        int k = 4;
        System.out.println(canPartitionKSubsets.canPartitionKSubsets(nums, k));
    }
}
